package SortMethod;

import SortHelper.SortHelper;

public class InsertSortFirst {

    private InsertSortFirst(){}

    /**
     *插入排序
     * 分析：
     * 1、从第二个数开始索引
     * 2、让它和自己前面的数比，直到遇到比自己小的为止。
     * 因为前面的数都是有序的，遇到比自己小的，说明前面的都比自己小
     *
     * 实现：
     * 要设立两个循环，第一个循环要从头到尾，第二个要找前面的数
     */
    public static <E extends Comparable<E>> void sort(E[] arr){
        //从第二个数开始遍历到结束
        for (int i = 1; i < arr.length; i++) {
            //让当前的数和前面的数比较，遇到比自己大的就换位，遇到比自己小的就直接退出
            //循环结束肯定前面都比自己小，后面都比自己大
            for (int j = i; j > 0 ; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0)
                    SortHelper.swap(arr,j,j-1);
                else break;
            }
        }

    }
}
